package leetcode.editor.cn;

//给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "aacecaaa"
//输出："aaacecaaa"
// 
//
// 示例 2： 
//
// 
//输入：s = "abcd"
//输出："dcbabcd"
// 
//
// 
//
// 提示： 
//
// 
// 0 <= s.length <= 5 * 10⁴ 
// s 仅由小写英文字母组成 
// 
// Related Topics 字符串 字符串匹配 哈希函数 滚动哈希 👍 407 👎 0

import java.util.Arrays;

//Java：最短回文串
public class ShortestPalindrome_214{
    public static void main(String[] args) {
        Solution solution = new ShortestPalindrome_214().new Solution();
        // TO TEST
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public String shortestPalindrome(String s) {
        int len = s.length();
        if (len ==0) return s;
        String strv = new StringBuffer(s).reverse().toString();
        String str = s+"#"+strv;
        char[] ss = str.toCharArray();
        int[] next = new int[len*2+1];
        for (int i = 1,j=0; i < 2*len+1; i++) {
            while(j>0 && ss[i]!=ss[j])
                j = next[j-1];
            if(ss[i]==ss[j]) j++;
            next[i] =j;
        }
        System.out.println(Arrays.toString(next));
        return new StringBuffer(strv.substring(0,len-next[2*len])).append(s).toString();
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
